HW#1 --- last modified March 02 2019 21:30:58..

Solution set.

Due date: Sep 11

Files to be submitted:
  Hw1.tex
  Hw1.zip

Purpose: To refresh our knowledge of O, Ω, Θ notation. To explore the relationship between decision problems and optimization problems. To begin studying formal machine models.

Related Course Outcomes: We are learning about the machine models needed for outcome (1) Exhibit a simulation of one machine model with another.

Specification:

This homework consists of two parts: a written answer part (the first three items below) and a coding part (the last numbered item below). I expect you to work in groups of up to three people. Do not share code or solutions between groups. The written part of the homework should be typeset in LaTeX and submitted as Hw1.tex. Your coding project should be submitted in the ZIP file Hw1.zip.

1. Prove carefully that (a) ∑ⁿ_i=1(1/i) = O(log n). (b) n! = Ω(n¹⁰⁰⁰⁰). (c) ∑ⁿ_i=0(i*n³) = Θ(n⁵).

2. Assume we are working over a unary alphabet I. Give the formal description of a Turing Machine which decides if the input is a power of 3.

3. Analyze the proof of Theorem 2.1 in the book to determine the space complexity of the algorithm given for simulating a k-tape Turing Machine by a 1-tape Turing Machine. Justify your answer.

4. For the coding parting of the assignment, you will implement the algorithm for MATCHING described in Chapter 1 of the book. After being compiled with the command javac *.java, your program will be run from the command line with a command like:

java Matching adjacency_string0 adjacency_string1 adjacency_string2 ...

For example,

java Matching "1 2 3" "2 4" "3" "0" "0 1 2 3 4"

The command line arguments are supposed to represent a bipartite graph. Let U={u₀, u₁, ..., u_n} and V={v₀, v₁, ..., v_n} be the disjoints sets of this graph. Then adjacency_stringi lists all the nodes in V connected to u_i. So for example, the string "1 2 3" in above says that u₀ is connected by an edge to v₁, v₂, v₃. You can assume that the number of nodes in U and V is the same as the number of strings listed as input. You do not need to check for illegal inputs.

Based on these inputs, your program should construct the capacity matrix of the 2n+2 node network which results from using the reduction in the book from MATCHING to MAX FLOW(D). For simplicity in this network we will label the nodes from U as 0 to n-1, the nodes from V from n to 2n-1, the node s will be node 2n, and the node t will be node 2n+1. Your program should then pretty print to the screen this matrix.

For the example command line above, one might get:

0 0 0 0 0 0 1 1 1 0 0 0

0 0 0 0 0 0 0 1 0 1 0 0

0 0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0 0 0 0 0

0 0 0 0 0 1 1 1 1 1 0 0

0 0 0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0 0 1

1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

Your program should then construct a max flow (use the breadth first variant from the book) for the network you got and pretty print its capacities. Finally, your program should write `yes' if the max flow has value n or larger and print `no' otherwise. Here `yes' will mean the original bipartite graph had a matching and `no' will mean it didn't.

Point Breakdown